package com.example.question.list.list1;

/**
 * @Date 2023-07-07
 * @Author Jonathan
 */
public class Code16_25 {
    public static void main(String[] args) {
        Code16_25 code = new Code16_25();
        ListNode listNode = List.createList(new int[]{1, 2, 3, 4, 5, 6, 7, 8});
        ListNode kthNode = code.getKthNode(listNode, 3);
        System.out.println(kthNode);
        ListNode node = code.reverseKGroup(listNode, 3);

        List.printLink(node);
    }

    public ListNode reverseKGroup(ListNode head, int k) {
        ListNode slow = head;
        ListNode fast = head;
        ListNode kthNode = getKthNode(head, k);
        int listLength = getListLength(head);
        while (fast != null) {
            // 找到fast
            if (listLength < k) {
                break;
            }
            for (int i = 0; i < k; i++) {
                if (i == k - 1) {
                    ListNode slowLast = fast;
                    fast = fast.next;
                    slowLast.next = null;
                } else {
                    fast = fast.next;
                }
            }
            // 反转以slow为头结点的链表
            reverse(slow);
            // 反转之后slow就是尾结点了
            // 此时 slow的指向next指向谁取决于 以fast为头结点的链表的长度是否大于等于k
            listLength = listLength - k;
            if (listLength < k) {
                slow.next = fast;
            } else {
                slow.next = getKthNode(fast, k);
            }
            slow = fast;
        }
        return kthNode;
    }

    private int getListLength(ListNode head) {
        int length = 0;
        while (head != null) {
            head = head.next;
            length++;
        }
        return length;
    }

    private ListNode getKthNode(ListNode head, int k) {
        int index = 1;
        while (index < k) {
            index++;
            head = head.next;
        }
        return head;
    }


    private ListNode reverse(ListNode head) {
        if (head.next == null) {
            return head;
        }
        ListNode ret = reverse(head.next);
        head.next.next = head;
        head.next = null;
        return ret;
    }
}
